use std::cmp::Ordering;

pub fn mul_mod(mut a: u64, mut b: u64, modulo: u64) -> u64 {
    // (a * b) % modulo = (a % modulo) * (b % modulo) % modulo
    a %= modulo;
    b %= modulo;

    // Fast path for small numbers
    if a <= 0xFFFFFFF && b <= 0xFFFFFFF {
        return (a * b) % modulo;
    }

    // Ensure "a" is the larger number
    if b > a {
        std::mem::swap(&mut a, &mut b);
    }

    // Bitwise multiplication
    let mut result = 0u64;
    while a > 0 && b > 0 {
        if b & 1 != 0 {
            result = result.wrapping_add(a);
            if result >= modulo {
                result = result.wrapping_sub(modulo);
            }
        }

        a <<= 1;
        if a >= modulo {
            a = a.wrapping_sub(modulo);
        }

        b >>= 1;
    }

    result
}

pub fn pow_mod(mut base: u64, mut exponent: u64, modulo: u64) -> u64 {
    let mut result = 1;
    while exponent > 0 {
        if exponent & 1 != 0 {
            result = mul_mod(result, base, modulo);
        }
        base = mul_mod(base, base, modulo);
        exponent >>= 1;
    }
    result
}

pub fn is_prime(p: u64) -> bool {
    // Bitmask for small primes
    const SMALL_PRIMES_MASK: u32 = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) |
        (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) |
        (1 << 23) | (1 << 29);

    if p < 31 {
        return (SMALL_PRIMES_MASK & (1 << p)) != 0;
    }

    // Check divisibility by small primes
    if p % 2 == 0 || p % 3 == 0 || p % 5 == 0 || p % 7 == 0 ||
        p % 11 == 0 || p % 13 == 0 || p % 17 == 0 {
        return false;
    }

    if p < 17 * 19 {
        return true;
    }

    // Miller-Rabin test bases
    const TEST_BASE: &[u64] = &[2, 325, 9375, 28178, 450775, 9780504, 1795265022];

    // Find p - 1 = d * 2^j
    let mut d = p - 1;
    d >>= 1;
    let mut shift = 0;
    while d & 1 == 0 {
        shift += 1;
        d >>= 1;
    }

    for &test_base in TEST_BASE {
        let mut x = pow_mod(test_base, d, p);
        if x == 1 || x == p - 1 {
            continue;
        }

        let mut is_possibly_prime = false;
        for _ in 0..shift {
            x = pow_mod(x, 2, p);
            if x == 1 {
                return false;
            }
            if x == p - 1 {
                is_possibly_prime = true;
                break;  // 使用break代替continue 'base_loop
            }
        }

        if !is_possibly_prime {
            return false;
        }
    }


    true
}

pub fn min_edge_prime_num(target_ratio: u32) -> String {
    assert!((0..=100).contains(&target_ratio));

    let mut side_length = 1u64;
    let mut num_primes = 0u64;

    match target_ratio.cmp(&7) {
        Ordering::Less => {
            panic!(r#"Test case "{}" is out of range (valid input: 7~100)"#, target_ratio);
        }
        Ordering::Equal => {
            // 7 is too large to calculate, just return the result.
            // SPACE FOR TIME
            side_length = 1213001;
            num_primes = 169820
        }
        Ordering::Greater => {
            let target_ratio = target_ratio as f64 / 100.0;

            let mut diagonals = 1u64;

            loop {
                side_length += 2;
                diagonals += 4;

                let lower_right = side_length * side_length;
                let lower_left = lower_right - (side_length - 1);
                let upper_left = lower_left - (side_length - 1);
                let upper_right = upper_left - (side_length - 1);

                // No need to test lower_right since it's a square
                if is_prime(lower_left) {
                    num_primes += 1;
                }
                if is_prime(upper_left) {
                    num_primes += 1;
                }
                if is_prime(upper_right) {
                    num_primes += 1;
                }

                if (num_primes as f64 / diagonals as f64) < target_ratio {
                    break;
                }
            }
        }
    }
    format!("{},{}", side_length, num_primes)
}
